package com.leetcode.algorithm.y22.m08.w2;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 450. 删除二叉搜索树中的节点
 * 
 * https://leetcode.cn/problems/delete-node-in-a-bst/
 * 
 * @author jie.deng
 *
 */
class Question0450Solution02 {

	public TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			// a.在root里找不到key
			return null;
		}
		if (root.val > key) {
			root.left = deleteNode(root.left, key);
			return root;
		} else if (root.val < key) {
			root.right = deleteNode(root.right, key);
			return root;
		}
	
		// root.val == key
		if (root.left == null && root.right == null) {
			// b.待删除节点是叶子节点
			return null;
		} else if (root.left == null) {
			// c.待删除节点无左孩子：使用右孩子替换之前的根节点
			return root.right;
		} else if (root.right == null) {
			// d.待删除节点无右孩子：使用左孩子替换之前的根节点
			return root.left;
		}
		// e.待删除节点有左孩子和右孩子：将右孩子作为根节点，左孩子作为右孩子左下角节点的左孩子
		TreeNode successor = root.right;
		while (successor.left != null) {
			successor = successor.left;
		}
		successor.left = root.left;
		return root.right;
	}

}